# -*- coding: utf-8 -*-
# @Time : 2024/2/18 9:54
# @Author : ZH
# @File : 889.py
# @Software: PyCharm

# Definition for a binary tree node.
from typing import List


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def constructFromPrePost(self, preorder, postorder):
        """
        :type preorder: List[int]  # 先序
        :type postorder: List[int]  # 后序
        :rtype: TreeNode
        """
        if not preorder or not postorder:
            return None
        # 先序遍历中 第一个元素为根节点
        root_val = preorder[0]
        root = TreeNode(root_val)
        if len(preorder) == 1:
            return root
        # 寻找后序遍历中元素的位置
        root_index = postorder.index(preorder[1])
        # print(root_val, preorder, postorder)
        root.left = self.constructFromPrePost(preorder=preorder[1:root_index+2], postorder=postorder[:root_index+1])
        root.right = self.constructFromPrePost(preorder=preorder[root_index+2:], postorder=postorder[root_index+1:-1])
        return root

if __name__ == '__main__':
    so = Solution()
    preorder = [1,2,4,5,3,6,7]
    postorder = [4,5,2,6,7,3,1]
    z = so.constructFromPrePost(preorder=preorder, postorder=postorder)
    print()

